/**
 * 队列(queue)是一种遵从先进先出(FIFO)原则的受限线性表（受限表示
 * 对结点的操作受限制）。新添加的元素在队列尾部（只能添加不能删除），
 * 待删除的元素在队列的首部（只能删除不能添加）。
 * 队列中没有元素时，称为空队列。
 */
export default class Queue<T> {
    private _items: any;
    private _count: number; // 队列里元素个数
    private _lowestIndex: number; // 尾部新元素即将使用的下标
    constructor() {
        this._items = {}; // 键名要求是非负整数
        this._count = 0;
        this._lowestIndex = 0; // 队列初始化，尾部新元素即将使用的下标当然是0了
    }
    /**
     * 向队列添加元素：向队列尾部添加一个（或多个）新的项
     */
    public enqueue(element: T) {
        this._items[this._lowestIndex] = element;
        this._count ++; // 元素新增
        this._lowestIndex ++; // 新增的元素会使“尾部新元素即将使用的下标”加一
    }
    /**
     * 从队列移除元素：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素
     */
    public dequeue(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        // 尾部新元素即将使用的下标减去元素个数就是首部元素的下标
        const headIndex = this._lowestIndex - this._count;
        const result = this._items[headIndex];
        delete this._items[headIndex];
        this._count --; // 元素移除，但不会影响“尾部新元素即将使用的下标”
        return result;
    }
    /**
     * 如果队列中不包含任何元素，返回true，否则返回false
     */
    public isEmpty(): boolean {
        return this._count === 0;
    }
    /**
     * 查看队列头元素：返回队列中第一个元素（最先被添加，准备最先被
     * 移除的元素），队列不做任何变动
     */
    public peek(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        return this._items[this._lowestIndex - this._count]; // 首部元素
    }
    /**
     * 查看队列目前的大小：返回队列包含的元素个数
     */
    public size(): number {
        return this._count;
    }
    /**
     * 清空队列
     */
    public clear() {
        this._items = {};
        this._count = 0;
        this._lowestIndex = 0;
    }
    /**
     * 队列的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const headIndex = this._lowestIndex - this._count; // 首部元素下标
        let objString: string = `${this._items[headIndex]}`; // 首部元素
        for (let i = 1; i < this._count ; i ++) {
            objString = `${objString},${this._items[headIndex + i]}`;
        }
        return objString;
    }
}
